This invention generally relates to memory management and, in particular, to a method and apparatus for facilitating memory management among heterogeneous elements of a program.
Legacy programming languages such as, for example, the Pascal, Fortran and C languages are well known. Developing source code using one of these legacy programming languages typically requires a programmer to embed instructions within their code to xe2x80x9cmanuallyxe2x80x9d manage the memory resources of the executing computer. That is a programmer writing source code in one of these legacy languages must embed instructions within the code to allocate memory to support objects created during execution of the program, and must subsequently explicitly reclaim these resources when the stored object is no longer required. For small programs this manual memory management is an inconvenience for the programmer, but typically not overwhelming. However, as the size of a program and the number of simultaneously executing threads of a program increase, the programmer has a heightened burden to reclaim memory resources when the objects stored within such resources are no longer required by the program, i.e., xe2x80x9cgarbagexe2x80x9d or xe2x80x9cdeadxe2x80x9d objects.
Failure to reclaim memory allocated to dead objects may well result in the all too-familiar memory xe2x80x9coverflowxe2x80x9d and xe2x80x9cout of memoryxe2x80x9d conditions leading to the premature conclusion of an executing program. Historically, the manual management of memory resources, i.e., comprising static memory, stack memory and/or the heap, depending on the data structures employed by the programming language, has been prone to error for all but the most experienced and skilled programmers.
To alleviate this burden of memory management, more advanced programming languages have been developed that include automated memory management functions. Languages such as the Java(trademark) language by Sun Microsystems, the Standard ML (SML) language developed at Edinburgh University and implemented by Bell Laboratories (now Lucent Technologies), and the well-known LISP programming language developed at the Massachusetts Institute of Technology (MIT) each include automated memory reclamation functions within their runtime environment. In general, memory for objects (i.e., software xe2x80x9cbundlesxe2x80x9d of variables and related methods) is explicitly allocated on the heap by the program and implicitly reclaimed by a function of the runtime environment (e.g., the Java(trademark) Virtual Machine) when no longer needed. This process of implicitly reclaiming memory resources from dead objects is colloquially referred to as garbage collection.
Typically, the garbage collection function is implemented as an implicit function of the memory allocation function. That is to say, when a program attempts to create an object, the runtime environment accesses a xe2x80x9clistxe2x80x9d to ensure that adequate heap memory is available. If, while attempting to create an object it is determined that inadequate heap memory exists, the runtime environment invokes the garbage collection function to identify xe2x80x9cdeadxe2x80x9d objects, i.e., those objects no longer reachable by the program, and reclaim such memory for use by future objects.
A number of different garbage collection techniques exist, e.g., xe2x80x9ccopyingxe2x80x9d garbage collectors, xe2x80x9cmark-and-sweepxe2x80x9d garbage collectors and xe2x80x9cgenerationalxe2x80x9d garbage collectors to name a few. Although the techniques employed by these garbage collectors vary from one to another, they each generally employ a two-step garbage collection process of: (1) identifying dead objects on the heap; and (2) reclaiming memory associated with the dead objects.
To identify dead objects, the garbage collector performs a function colloquially referred to as xe2x80x9cwalking the stackxe2x80x9d for each thread within a program. To walk the stack, the garbage collector analyzes the xe2x80x9croot setxe2x80x9d, i.e., the static registers and stack memory for each thread of a program, to identify pointers to objects stored on the heap. The garbage collector follows these pointers to the objects within the heap, and follows any pointers embedded therein to further objects. In this way, the garbage collector may traverse several layers of object pointers to identify all live objects. It stands, therefore, that all objects which are not ultimately traceable back to the root set are unreachable by the program, i.e., a dead object, and is subject to garbage collection.
To reclaim memory from dead objects, the address(es) for memory allocated to dead objects are added to the list of available heap memory. Thus, when the program attempts to create a new object and the list is accessed, the heap memory currently allocated to a dead object is overwritten with the new xe2x80x9clivexe2x80x9d object.
Programming languages, such as the advanced programming languages introduced above, which include automated memory management features such as, for example, garbage collection, are often referred to as garbage collected languages. In contrast, programming languages that do not include this automated garbage collection feature. e.g., the legacy programming languages introduced above, are typically referred to as non-garbage collected languages.
Typical of innovations of convenience, the prevailing thought when these advanced programming languages were first developed is that they would be so widely accepted and embraced by the development community that they would replace the legacy programming languages, rendering code developed in legacy programming languages obsolete. Indeed, the advanced programming languages were and are widely embraced in the development community. However, experience shows that it is often more convenient, and sometimes necessary, to utilize code written in legacy programming languages than to attempt to xe2x80x9cre-writexe2x80x9d the code using an advanced language. For example, it may be more convenient or necessary for a program written in a garbage collected language to call an application program interface (API), or dynamic linked libraries (DLL) written in C/C++. Recognizing this need, nearly every runtime environment for an advanced programming language now provides a foreign function interface to support calls to xe2x80x9cforeign functionsxe2x80x9d (e.g., API""s, DLL""s and the like) written in legacy code.
Typically, the foreign function interface is an array of pointers to legacy functions, loaded as a library in the advanced programming language for the application. When making a call to a foreign function, the calling application typically provides an address to a re-entry point within the application. It must be appreciated by the developer utilizing the foreign language function call that when the call is made to the foreign function, the runtime environment for the advanced programming language is xe2x80x9csuspendedxe2x80x9d while the foreign function executes. As a consequence, the automated memory management facilities of the advanced programming language are similarly suspended. Any memory management that is performed during execution of the foreign function is in response to explicit memory management commands embedded within the foreign function. Insofar as the foreign function employs data structures that are different from, yet occupy the same address space as, the data structures of the advanced programming language, it is probable that the manual memory management of the foreign language function will corrupt pointers to objects stored within the heap, especially if the objects are utilized or referenced by the foreign function. As described above, the garbage collection function relies on such pointers to identify live objects on the heap. At best, corruption of the pointers retards the garbage collectors ability to reclaim memory from dead objects and, at worst, the corruption of the pointers may eliminate a reference to a live object that will be needed during the subsequent execution of the program. Indeed, the foreign function may even corrupt the objects themselves as it allocates and reclaims memory in support of its execution.
Currently, none of the foreign function interfaces associated with these advanced programming languages can ensure that pointers to live objects are maintained through a call to a foreign function. This limitation is significant in that it prevents the runtime environment of the advanced programming languages from supporting an arbitrary number of calls to and from foreign functions and still be able to perform automated memory management, i.e., garbage collection. Restated, although advanced programming languages support a call to a foreign function through a foreign code interface, it is at the cost of the automated memory management features of the advanced programming language.
Recognizing this limitation, some attempts at obvious solutions have been made to resolve this problem, i.e., to walk the stack for a program comprised of heterogeneous program components. In a first approach, frame pointers were used to walk the stack. Given a frame pointer fp for some call frame, (1) the address of its caller, i.e., the return address, is that memory location fp+4; and (2) the frame pointer for its caller is at memory location fp. Table 1, below, presents a function that walks the stack given the current value in the frame pointer register.
void stackWalk(char*origfp) {
char *fp=origfp;
do {
addr=*(fp+4);
fp=(char *) *fp;
/* process current frame */
process (addr,fp)
}while (fp is valid)
}
This approach does not work because compiled C functions, for example, may omit the frame pointer altogether. Consequently, when attempting to utilize frame pointers to walk the call stack for a thread comprised of heterogeneous program components, e.g., Java(trademark) components and C components, and certain of the program components fail to maintain the frame pointer, the automated memory management facility breaks down.
Under a second approach, an application program interface (API) that is included by the Microsoft Windows(copyright) operating system (from Microsoft Corp. of Redmond, Wash.) for obtaining a stack trace as part of the ImageHIp API is relied upon to walk the stack. Those skilled in the art will appreciate that this xe2x80x9cStackWalkxe2x80x9d API is designed to be used by debuggers in debugging tools, such as memory leak detectors. This approach does not work well for several reasons. First, the StackWalk API assumes that the thread whose stack it is walking is stopped. Consequently, in a single threaded case where the garbage collector tries to walk its own stack using the StackWalk API, garbage results are produced as the function from the stack changing underneath it. Even placing the garbage collector on a separate thread does not necessarily solve the problem, as garbage collection typically runs while the system is in a safe state but not necessarily when all threads are stopped. Third, the StackWalk API has no way of detecting that it has reached the end of the stack. In fact, when running sample programs, the API walked off the stack for one of the callback threads and returned an incorrect value for the frame pointer to the garbage collector. Finally, use of the StackWalk API leads to a serious performance degradation. As a consequence, this otherwise obvious approach was deemed unacceptable for implementation.
The problem with the above solutions is that each make certain assumptions about the operation and/or memory management employed by the non-garbage collected language program component. That is, each of the foregoing solutions may have worked were it feasible, or even possible, to modify the foreign function to conform to these assumptions. Given, however, that the source code for Windows API""s and DLL""s are not typically available for modification to conform to these assumptions, the above solutions are not feasible.
Accordingly, a method and system supporting automated memory management in a program of heterogeneous program components is required that does not make any assumptions about the operation and/or memory management employed by any non-garbage collected program components. Just such a solution is provided below.
This invention generally concerns a method and system for facilitating automated memory management among heterogeneous components of a computer program.
According to a first aspect of the present invention, a method facilitating garbage collection in a program comprising heterogeneous program components is presented. The method begins by identifying transition points between the heterogeneous program components. A transition function is positioned at each transition point to maintain a history of select pointer and state information throughout program execution. By preserving a history of select pointer and state information, the transition function facilitates an arbitrary number of calls between two or more heterogeneous program components without the loss of pointer information necessary for a garbage collection function to accurately identify live objects.
The transition function, as will be described more fully below, is actually comprised of a creation function and a restoration function. The creation function creates a transition record during a transition from a first program component type and a second program component type. The creation function then populates the newly created transition record with select pointer and state information, and stores a pointer to the new transition record in the per-thread state, before continuing to the second program component type.
Upon return from the second program component type to the first program component type, the restoration function is invoked. The restoration function accesses the per-thread state for each thread executing within the program and loads the pointer to the transition record. The restoration function then pops the transition record and restores the pointer and state information contained therein. In addition, the restoration function then stores a pointer to an immediate prior transition record in the per-thread state.
By selectively invoking an appropriate one of the transition functions, the pointer and state information necessary to support garbage collection is maintained across heterogeneous program components. According to a first implementation, the transition function is automatically added to the compiled code for the heterogeneous program by an innovative compiler. The compiler includes an analysis agent, which receives the source code and identifies transition points. The analysis function then automatically generates the appropriate code to integrate with the received program to implement an appropriate transition function at the transition point. Thus, if a creation function is required, the analysis agent interjects code to implement the creation function. Likewise, if the restoration function is called for, the analysis agent automatically generates and places the code required to implement the restoration function.
In an alternate implementation, the transition functions may well be incorporated into the runtime environment for the programming language. That is, the runtime environment includes an analysis agent which detects transition points in the executing heterogeneous program. At such transition points, the analysis agent of the runtime environment invokes instances of the creation function or the restoration function, according to the teachings of the present invention. Accordingly, it is to be appreciated that the present invention may well be practiced in alternate forms without deviating from the spirit and scope of the present invention.